package 算法.leetcode.array;

import java.util.Arrays;

/**
 * @author lchenglong
 * @date 2022/5/11
 */
public class ThreeSumClosest {

    public static void main(String[] args) {
        ThreeSumClosest instance = new ThreeSumClosest();
        int[] nums = new int[]{1,1,-1,-1,3};
        int target = -1;
        int ans = instance.threeSumClosest(nums, target);
        System.out.println(ans);
    }

    public int threeSumClosest(int[] nums, int target) {
        int ans = Integer.MAX_VALUE>>2;
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++) {
            int k = nums.length - 1;
            for (int j = i + 1; j < k;) {
               int sum = nums[i] +nums[j] +nums[k];
               if (Math.abs(sum - target)<Math.abs(ans-target)){
                   // 选择更接近的三数之和
                   ans = sum;
               }
                if (sum>target){
                    // 比target大
                   --k;
                } else {
                    ++j;
                }
            }
        }
        return ans;
    }
}
